package dp.beibao;

/**
 * 有一堆石头，每块石头的重量都是正整数。
 *
 * 每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为x 和y，且x <= y。那么粉碎的可能结果如下：
 *
 * 如果x == y，那么两块石头都会被完全粉碎；
 * 如果x != y，那么重量为x的石头将会完全粉碎，而重量为y的石头新重量为y-x。
 * 最后，最多只会剩下一块石头。返回此石头最小的可能重量。如果没有石头剩下，就返回 0。
 *
 * 
 *
 * 示例：
 *
 * 输入：[2,7,4,1,8,1]
 * 输出：1
 * 解释：
 * 组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]，
 * 组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]，
 * 组合 2 和 1，得到 1，所以数组转化为 [1,1,1]，
 * 组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。
 *
 */
public class leetcode1049_lastStoneWeightII {
    // 类似于分割等和子集可以用01背包！
    // 这里的本质也是要尽量均匀的将元素分为两部分
    // 石头的重量，可以理解为物品的重量和物品的价值
    // 要求的和，就是背包的容量
    // 而数组的值，就是背包的价值

    public int lastStoneWeightII(int[] stones) {
        if(stones.length == 0){
            return 0;
        }
        int sum = 0;
        for (int stone : stones) {
            sum += stone;
        }
        int target = sum/2;
        // f[j] 表示，容量为j的背包，最多可以背f[j]这么多价值的石头，而这里价值就是石头的重量。
        // j 表示背包容量
        // f[j] 表示实际背包里的重量（实际的价值）
        int[] f = new int[target + 1];
        /**
         * 其实这个循环也可以这么理解。
         * 当i 第一次循环时，选的是第一块石头
         * 当j 循环时f[j] 都会被相应的赋值，而没被赋值时，初始化都是0；
         * 当i 第二次循环时，选的是第二块石头
         * 当j 循环时f[j] 都会被相应的赋值，而在Math.max中的f[j] 是上一次循环的值，这里的比较是和上一次循环的比较。
         * 说白了就是我们需要对每个物品，都要选择是放还是不放。这就理解了。
         */
        for (int i = 0; i < stones.length; i++) {
            for (int j = target; j >= stones[i]; j--) {
                                    // 这里可以理解为 f[j - weigjt[i]] + value[i]；
                f[j] = Math.max(f[j],f[j - stones[i]] + stones[i]);
            }
        }

        return sum - f[target] - f[target];

    }

    public int lastStoneWeightII2(int[] stones) {
        /**
         * 本题其实就是尽量让石头分成重量相同的两堆，
         * 相撞之后剩下的石头最小，这样就化解成01背包问题了。
         *
         * 本题物品的重量为store[i]，物品的价值也为store[i]。
         * 1. 确定dp数组以及下标的含义
         *  dp[j]表示容量（这里说容量更形象，其实就是重量）为j的背包，最多可以背dp[j]这么重的石头。
         * 2. 01背包的递推公式为：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
         *    本题则是：dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
         * 3. 数组初始化
         * 既然 dp[j]中的j表示容量，那么最大容量（重量）是多少呢，就是所有石头的重量和。
         *
         * 因为提示中给出1 <= stones.length <= 30，1 <= stones[i] <= 1000，所以最大重量就是30 * 1000 。
         *
         * 而我们要求的target其实只是最大重量的一半，所以dp数组开到15000大小就可以了。
         *
         * 当然也可以把石头遍历一遍，计算出石头总重量 然后除2，得到dp数组的大小。
         *
         * 我这里就直接用15000了。
         * 接下来就是如何初始化dp[j]呢，因为重量都不会是负数，所以dp[j]都初始化为0就可以了，
         * 这样在递归公式dp[j] = max(dp[j], dp[j - stones[i]] + stones[i])中dp[j]才不会初始值所覆盖。
         *
         *
         */
        if(stones.length == 0){
            return 0;
        }
        int sum = 0;

        for (int stone : stones) {
            sum += stone;
        }

        int target = sum/2;
        //dp[j]表示容量（这里说容量更形象，其实就是重量）为j的背包，最多可以背dp[j]这么重的石头。
        int[] dp = new int[target + 1];

        for (int i = 0; i < stones.length; i++) {
            for (int j = target; j >= stones[i] ; j--) {
                dp[j] = Math.max(dp[j],dp[j - stones[i]] + stones[i]);
            }
        }

        return sum - dp[target] - dp[target];
    }

}
